import java.util.Scanner;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-10-16
 * Time: 14:50
 */

/**
 *  用栈求解迷宫问题
 *      试错法,  创建一个栈存储迷宫的路径, 对每一个位置 周边可走的位置进行试探, 如果能走就走到下一个可走的位置
 *      修改当前位置的di 为 试探的方位 ,再将下一个位置进栈,并且修改地图的标记,
 *      上下左右的四个位置都不可走
 *      就 出栈回退, 并修改当前地图的标记
 */
//每个位置的类
class node2 {
    int x;  //横坐标
    int y;  //纵坐标
    int di; //下一可走相邻方位的方位号

    public node2(int x, int y, int di) {
        this.x = x;
        this.y = y;
        this.di = di;
    }
}
public class Main2 {

    public static void main(String[] args) {

        if(!getMapPath()) {
            System.out.println("未找到");
        }

    }

    public static boolean getMapPath() {
        Scanner sc1 = new Scanner(System.in);
        int m = sc1.nextInt();
        int n = sc1.nextInt();
        //初始化迷宫
        int[][] maze = new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                maze[i][j] = sc1.nextInt();
            }
        }
        //创建一个栈,存放路径
        Stack<node2> stack = new Stack<>();
        Stack<node2> tmpstack = new Stack<>(); //辅助栈用来输出打印
        //创建一个节点,将入口先存入栈中
        node2 star = new node2(0,0,-1);
        stack.push(star);
        boolean flag = false;
        while(!stack.isEmpty()) {
            //先获取栈顶元素, 进行判断是否到达出口
            node2 tmp = stack.peek();
            int x = tmp.x;
            int y = tmp.y;
            int di = tmp.di;
            int x1 = 0,y1 = 0;
            boolean find = false;   //是否找到路的 标志位

            //遇到出口
            if( x == m-1 && y == n-1) {
                //直接出栈,输出的是 出口到入口的路径,创建一个数组,先出放出栈的 元素,再逆序输出数组
                //node2 []path = new node2[m*n];
                int k = 0;
                //弹出栈中的所有元素 存入数组中
                /*while( !stack.isEmpty()) {
                    path[k++] = stack.pop();
                }*/
                //输出路径
                for( int i=0;i<stack.size();i++) {
                    System.out.print("("+stack.get(i).x +"," + stack.get(i).y+") " + stack.get(i).di + "  ");
                }
                System.out.println("\n==============");
                /*//输出路径
                for( int i=k-1;i>=0;i--) {
                    System.out.print("("+path[i] +"," + stack.get(i)+")  " );
                }*/

               //求所有路径,先将终点重置为0

                node2 tmp3 = stack.pop();//弹出栈中存放的终点
                maze[tmp3.x][tmp3.y] = 0;
                flag = true;
            }
            find = false;
            //不是出口 ,按照 上0->右1->下2->左3的顺序进行试探
            while( di <4 ) {
                di++;
                switch (di) {
                    case 0: x1 = tmp.x-1;   y1 = tmp.y; break;    //试探上
                    case 1: x1 = tmp.x;     y1 = tmp.y+1; break;  //试探右
                    case 2: x1 = tmp.x+1;   y1 = tmp.y; break;    //试探下
                    case 3: x1 = tmp.x  ;   y1 = tmp.y-1; break;  //试探左
                }
                if( x1>=0 && x1<m && y1>=0 && y1<n && maze[x1][y1] == 0) { //不越界,且该位置为0,说明找到下一个能走的位置
                    find = true;
                    break;
                }
            }
            //找到下一个能走的位置
            if( find) {
                stack.peek().di = di;   //先修改当前的栈顶元素的di为 当前的di,表示当前di 这个方向已经走过了,不需要再走
                node2 tmp2 = new node2(x1,y1,-1);
                stack.push(tmp2);
                maze[x1][y1] = -1;    //修改迷宫的当前位置为-1, 表示该位置已经走过了
            } else {           //走到了死路,需要进行出栈 回退
                node2 e = stack.pop();
                maze[e.x][e.y] = 0;  //将地图中当前位置置为 0,说明已经 该位置还没走
            }

        }
        return flag;
    }
}
